package com.unionfind;

/**
 *
 * PH: path halving
 * @Author: tgy
 * @Date: 2020-10-20 13:36
 */
public class UnionFind_QU_R_PH extends UnionFind_QU_R {

    public UnionFind_QU_R_PH(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {

        checkV(v);

        while (parents[v] != v) {

            parents[v] = parents[parents[v]];
            v = parents[v];
        }

        return v;
    }
}
